package gold.digger;

import java.util.*;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC785 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public boolean isBipartite(int[][] graph) {
            Set<Integer> ASet = new HashSet<>();
            Set<Integer> BSet = new HashSet<>();
            boolean curASet = false;
            Queue<Integer> queue = new LinkedList<>();
            List<Integer> allStartNode = getAllStartNode(graph);
            for (Integer node : allStartNode) {
                queue.offer(node);
                ASet.add(node);//node add to set A.
            }

            while (!queue.isEmpty()) {
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    int curId = queue.poll();
                    for (int next : graph[curId]) {
                        if (curASet && BSet.contains(next)) return false;
                        if (!curASet && ASet.contains(next)) return false;
                        if (curASet) {
                            if (ASet.contains(next)) continue;
                            else ASet.add(next);
                        }
                        if (!curASet) {
                            if (BSet.contains(next)) continue;
                            else BSet.add(next);
                        }

                        queue.offer(next);
                    }
                }


                curASet = !curASet;//oppose set indicator.
            }

            return ASet.size() + BSet.size() == graph.length;
        }

        public List<Integer> getAllStartNode(int[][] graph) {
            List<Integer> startNodeList = new ArrayList<>();

            Queue<Integer> queue = new LinkedList<>();
            Set<Integer> coverSet = new HashSet<>();
            for (int i = 0; i < graph.length; i++) {
                coverSet.add(i);
            }

            boolean[] visited = new boolean[graph.length];
            while (coverSet.size() > 0) {
                Iterator cit = coverSet.iterator();
                int curStartId = ((int) cit.next());
                queue.offer(curStartId);
                startNodeList.add(curStartId);
                visited[curStartId] = true;

                cit.remove();
                while (!queue.isEmpty()) {
                    int curId = queue.poll();
                    for (int next : graph[curId]) {
                        if (visited[next]) continue;
                        coverSet.remove(next);
                        queue.offer(next);
                        visited[next] = true;
                    }
                }
            }

            return startNodeList;
        }
    }


    public void run() {
        Solution solution = new Solution();
//        int[][] graph = InputUtil.toDoubleIntegerArray("[[4],[],[4],[4],[0,2,3]]");
//        int[][] graph = {{1}, {0}, {4}, {4}, {2, 3}};
        int[][] graph = {{4}, {}, {4}, {4}, {0, 2, 3}};
        System.out.println(solution.isBipartite(graph));
    }

    public static void main(String[] args) throws Exception {
        LC785 an = new LC785();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
